#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int INF = 0x3f3f3f3f;

bool bmask[N];
int nx, ny, dis;
int cx[N], cy[N], dx[N], dy[N];
vector<int> g[N];

bool searchpath() {
    queue<int> Q;
    dis = INF;
    memset(dx, -1, sizeof(dx));
    memset(dy, -1, sizeof(dy));
    for(int i = 0; i < nx; i++)
        if(cx[i] == -1) Q.push(i), dx[i] = 0;
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        if(dx[u] > dis) break;
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if(dy[v] == -1) {
                dy[v] = dx[u] + 1;
                if(cy[v] == -1) dis = dy[v];
                else {
                    dx[cy[v]] = dy[v] + 1;
                    Q.push(cy[v]);
                }
            }}}
    return dis != INF;
}
bool findpath(int u) {
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(!bmask[v] && dy[v] == dx[u] + 1) {bmask[v] = 1;
            if(cy[v] != -1 && dy[v] == dis) continue;
            if(cy[v] == -1 || findpath(cy[v])) {
                cy[v] = u; cx[u] = v; return true;
            }}}
    return false;
}
int MaxMatch() {
    int res = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    while(searchpath()) {
        memset(bmask, 0, sizeof(bmask));
        for(int i = 0; i < nx; i++)
            if(cx[i] == -1)
                res += findpath(i);
    }
    return res;
}
